package com.sparrow.common.stringmatch.ac;

import java.util.*;

/**
 * AC 自动机 (Aho-Corasick Automaton)
 * 多模式字符串匹配
 *
 * 特点：
 * 1. 基于 Trie 树
 * 2. 每个节点多一个 fail 指针（失败指针）
 * 3. 匹配复杂度 O(n + 匹配数量)
 */
public class ACAutomaton {
    /**
     * 节点定义
     */
    static class ACNode {
        char c;
        boolean isEnd;
        Map<Character, ACNode> children = new HashMap<>();
        ACNode fail; // 失败指针
        String word; // 如果是结束点，存储完整单词

        ACNode(char c) {
            this.c = c;
        }
    }

    private final ACNode root = new ACNode('R');

    /**
     * 插入一个敏感词
     */
    public void insert(String word) {
        ACNode node = root;
        for (char ch : word.toCharArray()) {
            node = node.children.computeIfAbsent(ch, ACNode::new);
        }
        node.isEnd = true;
        node.word = word;
    }

    /**
     * 批量插入
     */
    public void load(List<String> words) {
        for (String word : words) {
            if (word != null && !word.isEmpty()) {
                insert(word.toLowerCase());
            }
        }
        buildFailPointers();
    }

    /**
     * 构建 fail 指针
     * 给 AC 自动机里的每个节点设置 失败指针，保证匹配失败时能快速跳转。广度优先遍历
     *  这段代码就是：
     * 从根开始 BFS。
     * 根的孩子 fail = 根。
     * 普通节点的孩子：
     * 沿着父亲的 fail 指针往上跳，
     * 找到能匹配当前字符的位置，
     *  设置为 fail 指针，找不到就指向根。
     *
     */
    private void buildFailPointers() {
        Queue<ACNode> queue = new ArrayDeque<>();
        root.fail = root;
        queue.add(root);

        while (!queue.isEmpty()) {
            ACNode node = queue.poll();

            for (Map.Entry<Character, ACNode> entry : node.children.entrySet()) {
                char ch = entry.getKey();
                ACNode child = entry.getValue();

                if (node == root) {
                    child.fail = root;
                } else {
                    ACNode fail = node.fail;
                    while (fail != root && !fail.children.containsKey(ch)) {
                        fail = fail.fail;
                    }
                    if (fail.children.containsKey(ch)) {
                        fail = fail.children.get(ch);
                    }
                    child.fail = fail;
                }

                queue.add(child);
            }
        }
    }

    /**
     * 匹配所有敏感词
     */
    public List<String> matchAll(String text) {
        List<String> result = new ArrayList<>();
        ACNode node = root;
        char[] chars = text.toLowerCase().toCharArray();

        for (char c : chars) {
            while (node != root && !node.children.containsKey(c)) {
                node = node.fail;
            }
            node = node.children.getOrDefault(c, root);

            ACNode temp = node;
            while (temp != root) {
                if (temp.isEnd) {
                    result.add(temp.word);
                }
                temp = temp.fail;
            }
        }
        return result;
    }

    /**
     * 匹配第一个敏感词
     */
    public String matchFirst(String text) {
        ACNode node = root;
        char[] chars = text.toLowerCase().toCharArray();

        for (char c : chars) {
            while (node != root && !node.children.containsKey(c)) {
                node = node.fail;
            }
            node = node.children.getOrDefault(c, root);

            ACNode temp = node;
            while (temp != root) {
                if (temp.isEnd) {
                    return temp.word;
                }
                temp = temp.fail;
            }
        }
        return "";
    }

    /**
     * 替换敏感词
     */
    public String filter(String text, char replaceChar) {
        StringBuilder sb = new StringBuilder(text);
        ACNode node = root;
        char[] chars = text.toLowerCase().toCharArray();

        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            while (node != root && !node.children.containsKey(c)) {
                node = node.fail;
            }
            node = node.children.getOrDefault(c, root);

            ACNode temp = node;
            while (temp != root) {
                if (temp.isEnd) {
                    int start = i - temp.word.length() + 1;
                    for (int j = start; j <= i; j++) {
                        sb.setCharAt(j, replaceChar);
                    }
                }
                temp = temp.fail;
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        ACAutomaton ac = new ACAutomaton();
        ac.load(Arrays.asList("he", "she", "hers", "his"));

        System.out.println("matchAll ushers: " + ac.matchAll("ushers")); // [she, he, hers]
        System.out.println("matchFirst ushers: " + ac.matchFirst("ushers")); // she
        System.out.println("filter ushers: " + ac.filter("ushers", '*')); // u****s
    }
}

